package top.jolyoulu.力扣._1073_负二进制数相加;
//给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
//
// 数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 +
// (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。
//
// 返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
//
//
//
// 示例 1：
//
//
//输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
//输出：[1,0,0,0,0]
//解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
//
//
//
//
//
// 示例 2：
//
//
//输入：arr1 = [0], arr2 = [0]
//输出：[0]
//
//
// 示例 3：
//
//
//输入：arr1 = [0], arr2 = [1]
//输出：[1]
//
//
//
//
// 提示：
//
//
//
// 1 <= arr1.length, arr2.length <= 1000
// arr1[i] 和 arr2[i] 都是 0 或 1
// arr1 和 arr2 都没有前导0
//
//
// Related Topics 数组 数学 👍 66 👎 0


import top.jolyoulu.utils.TimerUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
public class Answer1 {
    /*
        思路：
        基于二进制加法，逢二进一，基础上找规律
    */
    class Solution {

        public int[] addNegabinary(int[] arr1, int[] arr2) {
            List<Integer> ans = new ArrayList<>();
            int carry = 0; //进位
            int arr1Index = arr1.length - 1; //arr1下标
            int arr2Index = arr2.length - 1; //arr2下标
            while (arr1Index >= 0 || arr2Index >= 0 || carry != 0) {
                int x = carry;
                if (arr1Index >= 0) {
                    x += arr1[arr1Index];
                }
                if (arr2Index >= 0) {
                    x += arr2[arr2Index];
                }
                if (x >= 2) {
                    ans.add(x - 2);
                    carry = -1;
                } else if (x >= 0) {
                    ans.add(x);
                    carry = 0;
                } else {
                    ans.add(1);
                    carry = 1;
                }
                arr1Index--;
                arr2Index--;
            }
            //删除前导零
            while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
                ans.remove(ans.size() - 1);
            }
            //翻转数组
            int[] res = new int[ans.size()];
            for (int i = ans.size() - 1, j = 0; i >= 0; i--, j++) {
                res[j] = ans.get(i);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Answer1().new Solution();
//        System.out.println("用例1=======================================");
//        TimerUtils.timer(
//                () -> {
//                    Object[] b = new Object[2];
//                    int[] arr1 = {1, 1, 1, 1, 1};
//                    int[] arr2 = {1, 0, 1};
//                    b[0] = arr1;
//                    b[1] = arr2;
//                    System.out.println("arr1 = " + Arrays.toString(arr1));
//                    System.out.println("arr2 = " + Arrays.toString(arr2));
//                    return b;
//                },
//                (b) -> solution.addNegabinary((int[]) b[0], (int[]) b[1]),
//                (res) -> System.out.println("结果：" + Arrays.toString(res))
//        );
//        System.out.println("用例2=======================================");
//        TimerUtils.timer(
//                () -> {
//                    Object[] b = new Object[2];
//                    int[] arr1 = {0};
//                    int[] arr2 = {0};
//                    b[0] = arr1;
//                    b[1] = arr2;
//                    System.out.println("arr1 = " + Arrays.toString(arr1));
//                    System.out.println("arr2 = " + Arrays.toString(arr2));
//                    return b;
//                },
//                (b) -> solution.addNegabinary((int[]) b[0], (int[]) b[1]),
//                (res) -> System.out.println("结果：" + Arrays.toString(res))
//        );
//        System.out.println("用例3=======================================");
//        TimerUtils.timer(
//                () -> {
//                    Object[] b = new Object[2];
//                    int[] arr1 = {0};
//                    int[] arr2 = {1};
//                    b[0] = arr1;
//                    b[1] = arr2;
//                    System.out.println("arr1 = " + Arrays.toString(arr1));
//                    System.out.println("arr2 = " + Arrays.toString(arr2));
//                    return b;
//                },
//                (b) -> solution.addNegabinary((int[]) b[0], (int[]) b[1]),
//                (res) -> System.out.println("结果：" + Arrays.toString(res))
//        );
        System.out.println("用例4=======================================");
        new TimerUtils<Object[],int[]>().timer(
                () -> {
                    Object[] b = new Object[2];
                    int[] arr1 = {1};
                    int[] arr2 = {1};
                    b[0] = arr1;
                    b[1] = arr2;
                    System.out.println("arr1 = " + Arrays.toString(arr1));
                    System.out.println("arr2 = " + Arrays.toString(arr2));
                    return b;
                },
                (b) -> solution.addNegabinary((int[]) b[0], (int[]) b[1]),
                (res) -> System.out.println("结果：" + Arrays.toString(res))
        );
    }
}
//leetcode submit region end(Prohibit modification and deletion)